#define _CRT_SECURE_NO_WARNINGS 1

typedef struct sl
{
    char* a;
    int sz;
    int max;
}sl;

void slinit(sl* cl)
{
    cl->a = (char*)malloc(sizeof(sl) * 10);
    cl->sz = -1;
    cl->max = 10;
}

void slpush(sl* cl, char c)
{
    if (cl->sz + 1 == cl->max)
    {
        sl* psl = (char*)realloc(cl->a, cl->max * sizeof(sl) * 2);
        if (psl != NULL)
        {
            cl->a = psl;
            cl->max = cl->max * 2;
        }
        else
        {
            exit(1);
        }
    }
    cl->a[cl->sz + 1] = c;
    cl->sz++;

}

char slpop(sl* cl, char ri)
{
    if (cl->sz == -1)
    {
        return 'n';
    }
    else {
        if (cl->a[cl->sz] == '(')
        {
            if (ri == ')')
            {
                cl->sz--;
                return 'y';
            }
        }
        else if (cl->a[cl->sz] == '[')
        {
            if (ri == ']')
            {
                cl->sz--;
                return 'y';
            }
        }
        else if (cl->a[cl->sz] == '{')
        {
            if (ri == '}')
            {
                cl->sz--;
                return 'y';
            }

        }
        return 'n';
    }
}

void slDest(sl* cl)
{
    free(cl->a);
}

bool isValid(char* s) {
    int ri = 0;
    sl cl;
    slinit(&cl);
    char yn = 0;

    while (*(s + ri) != '\0')
    {
        if (*(s + ri) == '(' || *(s + ri) == '[' || *(s + ri) == '{')
        {
            slpush(&cl, *(s + ri));
        }
        else
        {
            yn = slpop(&cl, *(s + ri));
            if (yn == 'n')
                return false;
        }
        ri++;
    }
    if (cl.sz == -1)
    {
        slDest(&cl);
        return true;
    }
    else
    {
        slDest(&cl);
        return false;
    }
}